package a00_LeetCode.TopK;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Author quan
 * @Description 找出数组汇总最小的K个数：取小用大，取大用小（取较小的数字用大堆，取大数用小堆）
 * @Date 2023/4/3 10:45
 */
public class Num17_14_SmallestK {
    /**
     * 方法1：排序法：将数组中的所有元素排序，取出前k个即可
     */
    /*public int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);
        int[] result = new int[k];
        for (int i = 0; i < arr.length; i++) {
            result[i] = arr[i];
        }
        return result;
    }*/
    /**
     * 方法2：将数组中的元素都添加到最小堆里面，依次出堆k次。（因为最小堆的堆顶保存的一定是最小值）
     */
    /*public int[] smallestK(int[] arr, int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (int i : arr) {
            queue.offer(i);
        }
        int[] result = new int[k];
        for (int i: arr) {
            result[i] = arr[i];
        }
        return result;
    }*/
    /**
     * 方法3：设计一个时间复杂度小于n*logn的算法
     * 建立一个只保存k个元素的最大堆，扫描整个数组。
     * Step1:若当前最大堆的元素个数小于k,直接入队；Step2:当最大堆的元素个数>=K时，如果当前元素最大堆的堆顶还大，则一定不是需要的元素。
     */
    public int[] smallestK(int[] arr, int k) {
        //JDK默认为最小堆实现，此时改造为最大堆:使用比较器对象
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        if(k == 0){
            return new int[0];
        }
        //Step1
        for (int i = 0; i < arr.length; i++) {
            if(i < k){
                queue.offer(arr[i]);
            }else{//Step2
                int maxValue = queue.element();//*************这里写成peek就一直在报错显示空指针异常！！！
                //注意：Queue 中 element() 和 peek()都是用来返回队列的头元素，不删除。
                //在队列元素为空的情况下，element() 方法会抛出NoSuchElementException异常，peek() 方法只会返回 null。
                if(arr[i] < maxValue){
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        //此时队列中保存了最小的K个值
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
           result[i] = queue.poll();
        }
        return result;
    }
}
